The present invention relates generally to diagnosing complex systems and devices including a large number of parts and components.
As today's technical systems generally become increasingly complex, efficient monitoring and detection of malfunctioning components is an area that gains progressive importance. Fault diagnosis algorithms may be applied to determine why an entity does not behave as intended. Typically, “diagnosing” the entity means selecting a subset of a predetermined set of causes responsible for the entity's incorrect behavior. A diagnosis must both explain the incorrect behavior and optimize some objective function, such as probability of correctness or cost of incorrect diagnosis. The need to diagnose is a common reason to measure or to test the entity. It is assumed that the entity consists of a finite number of diagnosed components. Moreover, it is normally presumed that failures of the entity are caused only by faults in at least one of these components.
In Reiter, R., “A theory of diagnosis from first principles”, Artificial Intelligence, 32(1):57.95, April, 1987 and deKleer, J. and Williams, B. C., “Diagnosing multiple faults” Artificial Intelligence, Issue 1, Volume 32: pp. 97.130, 1987, algorithms for finding all so-called minimal diagnoses are presented. Later, various improvements of these algorithms have also been described. The above-mentioned original algorithm and its associated framework as presented by deKleer and Williams presumes that the system to be diagnosed includes of a number of components being represented by a set C. Here, a conflict is represented as a set C⊂C. A conflict C is understood to mean that not all components in C can be in the fault-free mode. Moreover, a conflict C1 is said to be minimal if there is no other conflict C2 such that C2⊂C1.
A diagnosis δ is also represented as a set δ⊂C. The meaning of a diagnosis δ is that the components contained in δ are faulty and the components not contained in δ are fault-free. A diagnosis δ1 is said to be minimal if there is no other diagnosis δ2 such that δ2⊂δ1.
One fundamental relation between conflicts and diagnoses is that if  is the set of all minimal conflicts, then δ is a diagnosis if and only if for all conflicts Cε it holds that δ∩C≠Ø.
Given a set of diagnoses Δ and a conflict C the minimal hitting set algorithm according to deKleer and Williams finds an updated set of minimal diagnoses. Specifically, the algorithm as described by deKleer and Williams, can be written as follows.
Input: a set of minimal diagnoses Δ, and a conflict set C.
Output: an updated set of minimal diagnoses Θ.
Δold = Δfor all δi ∈ Δ doif δj ∩ C ≠ Ø; thenRemove δi from Δoldfor all c ∈ C doδnew := δi ∪ {c}for all δk ∈ Δ, δk ≠ δi doif δk⊂δnew; thengo to LABEL1end ifnextΔadd := Δadd ∪ {δnew}LABEL1nextend ifnextΘ := Δold ∪ Δadd
The algorithm has the properties that if Δ is the set of all minimal diagnoses, the algorithm output Θ will contain all minimal diagnoses with respect to also the new conflict C. Further, it holds that Θ will contain only minimal diagnoses.
These are certainly useful properties when monitoring and testing an entity. However, when determining the status of a complex entity, it is a severe limitation that each component may only have two possible behavioral modes, i.e. either be fault-free or be faulty. Instead, more specific fault statuses are desirable for improved diagnosis quality.